package binarySearch;

/**
 * @author pengfei.hpf
 * @date 2020/2/20
 * @verdion 1.0.0
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 *
 * 你的算法时间复杂度必须是 O(log n) 级别。
 *
 * 如果数组中不存在目标值，返回 [-1, -1]。
 *
 * 示例 1:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 8
 * 输出: [3,4]
 * 示例 2:
 *
 * 输入: nums = [5,7,7,8,8,10], target = 6
 * 输出: [-1,-1]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class SearchRange {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[]{-1, -1};
        if(nums == null || nums.length == 0){
            return res;
        }
        int find = bs(nums, target, 0, nums.length - 1);
        if(nums[find] != target){
            return res;
        }
        if(find == 0){
            res[0] = 0;
        } else {
            int start = find;
            int r = find - 1;
            while(r >= 0 && nums[r] == nums[start]){
                start = bs(nums, target, 0, r);
                r = start - 1;
            }
            res[0] = start;
        }
        if(find == nums.length - 1){
            res[1] = nums.length - 1;
        } else {
            int end = find;
            int l = find + 1;
            while(l <= nums.length - 1 && nums[l] == nums[end]){
                end = bs(nums, target, l, nums.length - 1);
                l = end + 1;
            }
            res[1] = end;
        }
        return res;
    }

    private int bs(int[] nums, int target, int l, int r){

        while(l < r){
            int mid = l + (r - l)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                r = mid;
            }else{
                l = mid + 1;
            }
        }
        return l;
    }
}
